home *** CD-ROM | disk | FTP | other *** search
/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Ebooks / Thinking in C++ V2 / C20 / PriorityQueue5.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2000-05-25  |  998 b   |  44 lines
  1. //: C20:PriorityQueue5.cpp
  2. // From Thinking in C++, 2nd Edition
  3. // Available at http://www.BruceEckel.com
  4. // (c) Bruce Eckel 1999
  5. // Copyright notice in Copyright.txt
  6. // Building your own priority queue
  7. #include <iostream>
  8. #include <queue>
  9. #include <cstdlib>
  10. #include <ctime>
  11. using namespace std;
  12.  
  13. template<class T, class Compare>
  14. class PQV : public vector<T> {
  15.   Compare comp;
  16. public:
  17.   PQV(Compare cmp = Compare()) : comp(cmp) {
  18.     make_heap(begin(), end(), comp);
  19.   }
  20.   const T& top() { return front(); }
  21.   void push(const T& x) {
  22.     push_back(x);
  23.     push_heap(begin(), end(), comp);
  24.   }
  25.   void pop() {
  26.     pop_heap(begin(), end(), comp);
  27.     pop_back();
  28.   }  
  29. };
  30.  
  31. int main() {
  32.   PQV<int, less<int> > pqi;
  33.   srand(time(0));
  34.   for(int i = 0; i < 100; i++)
  35.     pqi.push(rand() % 25);
  36.   copy(pqi.begin(), pqi.end(),
  37.     ostream_iterator<int>(cout, " "));
  38.   cout << endl;
  39.   while(!pqi.empty()) {
  40.     cout << pqi.top() << ' ';
  41.     pqi.pop();
  42.   }
  43. } ///:~
  44.